import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=77 lang=java
 *
 * [77] 组合
 */

// @lc code=start
class Solution {
    LinkedList<Integer> path;
    List<List<Integer>> res;
    public List<List<Integer>> combine(int n, int k) {
          path=new LinkedList<>();
          res=new ArrayList<>();
          dfs(n, k, 1);
          return res;
    }
    public void dfs(int n,int k,int startIndex){
        if(path.size()==k){
            res.add(new LinkedList<>(path));//迷惑点
            return;
        }
        for(int i=startIndex;i<=n-(k-path.size())+1;i++){
            path.add(i);
            dfs(n, k, i+1);
            path.removeLast();
        }
    }
}
//解惑：
//  res.add(new ArrayList(path))：开辟一个独立地址，地址中存放的内容为path链表，后续path的变化不会影响到res
//   res.add(path)：将res尾部指向了path地址，后续path内容的变化会导致res的变化。
// https://blog.csdn.net/weixin_42707971/article/details/107609388#:~:text=res.add%20%28new,ArrayList%20%28path%29%29%20%EF%BC%9A%E5%BC%80%E8%BE%9F%E4%B8%80%E4%B8%AA%E7%8B%AC%E7%AB%8B%E5%9C%B0%E5%9D%80%EF%BC%8C%E5%9C%B0%E5%9D%80%E4%B8%AD%E5%AD%98%E6%94%BE%E7%9A%84%E5%86%85%E5%AE%B9%E4%B8%BApath%E9%93%BE%E8%A1%A8%EF%BC%8C%E5%90%8E%E7%BB%ADpath%E7%9A%84%E5%8F%98%E5%8C%96%E4%B8%8D%E4%BC%9A%E5%BD%B1%E5%93%8D%E5%88%B0res
// @lc code=end

